# 作者：lian
import random
import time
import sys
sys.setrecursionlimit(10000000)

class Sort:
    def __init__(self, n):
        self.len = n
        self.arr = [87, 41, 63, 51, 41, 50, 90, 38, 59, 83]
        # self.random_data()


    # def random_data(self):
    #     for i in range(self.len):
    #         self.arr[i] = random.randint(0,99)

    def partition(self,left,right):
        arr = self.arr
        k=i=left
        for i in range(left,right):
            if arr[i]<arr[right]:
                arr[i],arr[k]=arr[k],arr[i]
                k+=1
        arr[k],arr[right]=arr[right],arr[k]
        return k

    def quickSort(self,left,right):
        if left<right:
            pivot = self.partition(left,right)
            self.quickSort(left,pivot - 1)
            self.quickSort(pivot + 1,right)

    def adjust_max_heap(self,pos,arr_len):
        arr = self.arr
        dad = pos
        son = 2*dad + 1
        while son < arr_len:
            if son + 1 < arr_len and arr[son] < arr[son + 1]:
                son += 1 #将son指向较大的那个节点
            if arr[son] > arr[dad]:
                arr[dad],arr[son] = arr[son],arr[dad]
                #如果交换，则更新son和dad
                dad = son
                son = 2*dad + 1
            else:
                break
    def heap_sort(self):
        for parent in range(self.len // 2 - 1,-1,-1):
            self.adjust_max_heap(parent,self.len)
        arr = self.arr
        arr[0],arr[self.len-1]=arr[self.len-1],arr[0] #交换堆顶元素和最后一个元素
        for arr_len in range(self.len-1,1,-1):
            self.adjust_max_heap(0,arr_len)
            arr[0],arr[arr_len-1] = arr[arr_len-1],arr[0]

    def test_time_use(self,sort_func,*args,**kwargs):
        start = time.time()
        sort_func(*args,**kwargs)
        end = time.time()
        print(f'总计用时{end - start}')

if __name__ == '__main__':
    count = 100000
    my_sort = Sort(count)


list.sort()

